package interview.pathsum;

import java.util.ArrayList;

public class PathSum {
	public void paths(Node root, int sum, ArrayList<Path> paths) {
		if (root == null) {
			return;
		}

		ArrayList<Node> fromRoot = new ArrayList<Node>();
		pathsFromRoot(root, sum, fromRoot);
		for (Node node : fromRoot) {
			paths.add(new Path(root, node));
		}

		ArrayList<Path> notFromRoot = new ArrayList<Path>();
		paths(root.left, sum, notFromRoot);
		paths.addAll(notFromRoot);

		notFromRoot.clear();
		paths(root.right, sum, notFromRoot);
		paths.addAll(notFromRoot);
	}

	private void pathsFromRoot(Node root, int sum, ArrayList<Node> nodes) {
		if (root == null) {
			return;
		}

		sum -= root.data;
		if (sum == 0) {
			nodes.add(root);
		}

		pathsFromRoot(root.left, sum, nodes);
		pathsFromRoot(root.right, sum, nodes);
	}
}